﻿// Amount of Degrees 度的数量.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>


using namespace std;

/*
* https://loj.ac/p/10163
* http://ybt.ssoier.cn:8088/problem_show.php?pid=1585
* 
题目描述
原题来自：NEERC 2000 Central Subregional，题面详见 Ural 1057。

求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。
例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：
17 = 2^4+2^0
18 = 2^4 + 2^1
20 = 2^4+2^2



输入格式
第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。

输出格式
只包含一个整数，表示满足条件的数的个数。

样例
输入
15 20
2
2
输出
3
*/

const int N = 32;
int f[N][N];

int l, r;
int k, b;

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (!j) f[i][j] = 1;
			else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
		}
	}

}
 

int dp(int x) {
	if (!x) return 0;
	vector<int> vv;
	while (x != 0) {
		vv.push_back(x % b);
		x = x / b;
	}

	int res = 0;
	int last = 0;
	for (int i = vv.size() - 1; i >= 0; i--) {
		int t = vv[i];
		if (t) {
			res += f[i][k - last];
			if (t > 1) {
				if (k - last - 1 >= 0) res += f[i][k - last - 1];
				last++;
				break;
			}
			else {
				last++;
				if (last > k) break;
			}
		}

		if (!i && last == k) res++;
	}

	return res;
}




int main()
{
	init();
	cin >> l >> r >> k >> b;

	cout << dp(r) - dp(l - 1) << endl;

	return 0;
}

 